#include "Graph.h"
#include <stdio.h>



Graph::Graph(void)
{	
}

static vector<int> InverseVector(vector<int> Vector)
{
	int valeur;
	int n = Vector.size();
	double m = n;
	m = m/2;
	for (int i = 0; i<m; i++)
	{
		valeur = Vector[i];
		Vector[i] = Vector[n-i-1];
		Vector[n-i-1] = valeur;
	}
	return Vector;
}


/*constructor using a set of edges as an input*/
Graph::Graph(std::vector<Edge> Edges)
{
	
	/*find the number of nodes in the graph*/
	int edge_size = Edges.size();
	int Node_Max = 0;
	for (int i = 0; i<edge_size; i++)
	{
		Node_Max = MAX(Node_Max, MAX(Edges[i].Get_Index1(), Edges[i].Get_Index2()));
	}
	m_Nodes = Node_Max;

	/*creation of a matrix (m_MatrixEdges) with:
	m_MatrixEdges[i][j]= distance(i,j) if there exists an edge linking node i and node j
	m_MatrixEdges[i][j]= INFINITY if there is no edge linking node i and node j, or if i=j
	*/

	/*define the size of the matrix*/
	m_MatrixEdges.resize(m_Nodes);

	/*initialisation of m_MatrixEdges : setting all its components at INIFINITY*/
	for (int k = 0; k<m_Nodes;k++)
	{
		m_MatrixEdges[k].resize(m_Nodes,INFINITY);
	}

	/*filling m_MatrixEdges*/
	for (int j = 0; j<edge_size;j++)
	{
		int Ind1 = Edges[j].Get_Index1();
		int Ind2 = Edges[j].Get_Index2();
		m_MatrixEdges[Ind1-1][Ind2-1]=Edges[j].Get_Dist();
	}
}

/*Solve is the function that performs the Dijkstra algorithm using a starting node Init, a final node Final
and returning a vector Res=(path_length,path) where:
- path_length is the length of the shortest path between the starting and the final node
- path is the ordered set of nodes that needs visiting between the starting and the final node in order
to achieve the minimal distance Min
*/


vector<vector<int>> Graph::Dijkstra(int Init, int Final)
{
	/*vector of booleans of the form Visited[i-1]= "true" if node i has been visited, "false" otherwise */
	vector<bool> Visited; 
	Visited.resize(m_Nodes,false); /*initialisation Visited[i-1]= "false" for all i*/

	/*vector of integer such that Prev[i-1] is the node just preceeding node i in the shortest path going from Init to node i*/
	vector<int> Prev;
	Prev.resize(m_Nodes,-1);
	Visited[Init-1]=true; /*the only node visited is the intial node Init*/

	/*Matrix is a matrix initialized with m_MatrixEdges that will successively display the shortest path from Init to Final*/
	vector<vector<int>> Matrix = m_MatrixEdges;
	vector<vector<int>> Matrix2 = m_MatrixEdges;
	
	int Min,path_length=0;
	int Previous=Init;
	int Current_Node;
	vector<vector<int>> Res;
	Res.resize(2);
	Res[1].push_back(0);

	/*allows not to come back to the initial node*/
	for (int k=0;k<m_Nodes;k++)
	{
		Matrix[k][Init-1] = INFINITY;
	}

	/*main loop aiming at iteratively updating Matrix in order to find the shortest path between Init and Final*/
	while (Visited[Final-1]==false)
	{
		/*first step: identify, among all visited nodes, the shortest distance Min and the correponding nearest node Current_Node reachable*/
		Min= INFINITY;
		for (int i=0; i<m_Nodes; i++)
		{
			if (Visited[i]==true)
			{
				for (int j = 0; j<m_Nodes; j++)
				{
					if (Matrix[i][j]<Min)
					{
						Min = Matrix[i][j];
						Current_Node = j+1;
						if (Current_Node==Final){path_length=Min;}/*get the shortest distance between Init and Final*/
					}
				}
			}
		}

		/*second step: actualisation of Matrix:
		- list Current_Node as visited
		- set all the distances to an already visited node at INIFINITY
		- increment by Min all the distances of the nodes reachable from Current_Node
		- record in Prev the nearest antecedent of Current_Node
		*/
		
		/*Update of Prev[]*/
		Visited[Current_Node-1]=true;
		if(m_MatrixEdges[Previous-1][Current_Node-1]<INFINITY)
		{
			Prev[Current_Node-1] = Previous;
		}
		else
		{
			Prev[Current_Node-1] = Prev[Previous-1];
		}
		
		/*Update of Matrix*/
		for (int k=0;k<m_Nodes;k++)
		{
			Matrix[Current_Node-1][k] = MIN(INFINITY,Matrix[Current_Node-1][k] + Min);
			Matrix[k][Current_Node-1] = INFINITY;
		}
		Previous = Current_Node;
	}

	/*displays the response vector Res*/
	Res[0].push_back(Current_Node);
	while (Current_Node!=Init)
	{
		Res[0].push_back(Prev[Current_Node-1]);
		Current_Node = Prev[Current_Node-1];
	}
	Res[0]= InverseVector(Res[0]);
	for (unsigned int b=0;b<(Res[0].size()-1);b++)
	{
		Res[1].push_back(Res[1][b] + Matrix2[Res[0][b]-1][Res[0][b+1]-1]);
	}
	return Res;
}


Graph::~Graph(void)
{
}
